#define _CRT_SECURE_NO_WARNINGS

//#include <stdio.h>
//#include <string.h>
//#include <stdlib.h>
//
//void _MergeSort(int left, int right, int* a, int* tmp)
//{
//    if (left >= right)
//        return;
//
//    int mid = (left + right) >> 1;
//    int begin1 = left, end1 = mid;
//    int begin2 = mid + 1, end2 = right;
//
//    _MergeSort(begin1, end1, a, tmp);
//    _MergeSort(begin2, end2, a, tmp);
//
//    int i = 0;
//    while (begin1 <= end1 && begin2 <= end2)
//    {
//        if (a[begin1] <= a[begin2])
//            tmp[i++] = a[begin1++];
//        else
//            tmp[i++] = a[begin2++];
//    }
//
//    while (begin1 <= end1)
//        tmp[i++] = a[begin1++];
//
//    while (begin2 <= end2)
//        tmp[i++] = a[begin2++];
//
//    memcpy(a + left, tmp, sizeof(int) * i);
//}
//
//int main()
//{
//    int N = 0;
//    scanf("%d", &N);
//
//    int arr[N];
//    for (int i = 0; i < N; ++i)
//    {
//        scanf("%d", &arr[i]);
//    }
//
//    int* tmp = malloc(sizeof(int) * N);
//    if (tmp == NULL)
//    {
//        perror("malloc fail");
//        exit(EXIT_FAILURE);
//    }
//    _MergeSort(0, N - 1, arr, tmp);
//
//    for (int i = 0; i < N; ++i)
//        printf("%d ", arr[i]);
//
//    free(tmp);
//    tmp = NULL;
//
//
//    return 0;
//}

//#include <stdio.h>
//#include <stdbool.h>
//#include <stdlib.h>
//
// struct ListNode 
// {
// 	int val;
// 	struct ListNode *next;
// };
// 
//typedef struct ListNode LTNode;
//
//LTNode* Middle(LTNode* phead)
//{
//    LTNode* fast = phead;
//    LTNode* slow = phead;
//
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//
//    return slow;
//}
//
//LTNode* Reverse(LTNode* phead)
//{
//    LTNode* newhead = NULL;
//    LTNode* pnext = NULL;
//
//    LTNode* pcur = phead;
//    while (pcur)
//    {
//        pnext = pcur->next;
//        if (newhead == NULL)
//        {
//            newhead = pcur;
//            newhead->next = NULL;
//        }
//        else
//        {
//            pcur->next = newhead;
//            newhead = pcur;
//        }
//
//        pcur = pnext;
//    }
//
//    return newhead;
//}
//
//bool chkPalindrome(struct ListNode* A)
//{
//    LTNode* pcur = A;
//    LTNode* newhead = Reverse(Middle(A));
//
//    while (pcur && newhead)
//    {
//        if (newhead->val != pcur->val)
//            return false;
//
//        newhead = newhead->next;
//        pcur = pcur->next;
//    }
//
//    return true;
//}
//
//int main()
//{
//    LTNode* n1 = (LTNode*)malloc(sizeof(LTNode));
//    LTNode* n2 = (LTNode*)malloc(sizeof(LTNode));
//    LTNode* n3 = (LTNode*)malloc(sizeof(LTNode));
//    LTNode* n4 = (LTNode*)malloc(sizeof(LTNode));
//    n1->next = n2;
//    n2->next = n3; 
//    n3->next = n4;
//    n4->next = NULL;
//    n1->val = 1, n2->val = 2, n3->val = 2, n4->val = 1;
//    
//    int ret = chkPalindrome(n1);
//    printf("%d\n", ret);
//
//    return 0;
//}


//bool _isSametree(struct TreeNode* root1, struct TreeNode* root2)
//{
//    if (root1 == NULL && root1 == root2)
//        return true;
//
//    if (!(root1 && root2))
//        return false;
//
//    if (root1->val != root2->val)
//        return false;
//
//    return _isSametree(root1->left, root2->left)
//        && _isSametree(root1->right, root2->right);
//}
//
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
//{
//    if (root == NULL)
//        return false;
//
//    if (_isSametree(root, subRoot))
//        return true;
//    else
//        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}












